import javax.swing.JLabel;
import java.util.ArrayList;
//  HEAP SORT: 
//  The main challange in implementing Heap Sort is to implement a fully functional
//  "Complete Binary Heap", after that it is easy. So first;
//  Complete Binary Heap = 
//  * Binary Tree, i.e. each branch has maximum 2 children 
//  * Complete Binary Tree, i.e. all levels except the deepest are filled,
//    and if last level is not complete, the nodes of that level are 
//    filled from left to right. (last lever filled = "balanced")
//  * Heap Property: each node is greater than to each of its children.
//  Insert Element: Put it in the next free leaf position and move it up (by swap)
//  until it is smaller than it's parent
//  Remove Element: Take away (and return) the TOP of the heap (i.e. the element
//  with biggest value) by swapping it with the last leaf. The top is now normally
//  not at all the biggest value. So "heapify" the heap again by moving it down by 
//  swapping it with the its child until it is larger than all its children 
//  Now we are ready for HEAP SORT: 
//  From an unsorted array insert the elements one by one into a heap (the elements
//  will automatically order itself with the heap property). Then Remove() elements
//  one by one from the heap and put into the array, starting at the last position
//  of the array. Remove() always gives the top (i.e. biggest element left in the 
//  heap) and automatically heapifies the heap again, so that the remaining biggest
//  elements ends up to the top. If the Heap works Heap Sort is very simple:
//     for (int i = 0; i < Ntot; i++) AddElement(heap, N, a[i]);
//     for (int i = Ntot-1; i >= 0; i--) a[i] = RemoveTop(heap, N);  
//  If the Heap is represented by an array follow these equalities
//     leftChild  = 2*parent + 1
//     rightChild = 2*parent + 2
//     parent     = (child - 1)/2
//  Worst, Average & Best: O(nlogn)
class HeapSort<T extends Comparable<T>> extends SortAlgorithm<T> { 
    HeapSort(JLabel listLabel, JLabel timeLabel, JLabel averageTimeLabel, JLabel statusLabel) { 
        super(listLabel, timeLabel, averageTimeLabel, statusLabel);
    }
    
    protected ArrayList<T> m_heap;
    
    @Override
    protected void sort() { 
        m_heap = new ArrayList<T>();
        int Ntot = m_list.size();
        //Heapify
	for (int i = 0; i < Ntot; i++) { addElement(m_list.get(i)); }
	//Put back the numbers in the list, backwards, m_heap is re-heapified everytime
	for (int i = Ntot-1; i >= 0; i--) { m_list.set(i, removeTop()); }
    }
    //Remove top, heapify and then return old top
    public T removeTop() { 
        if (m_heap.isEmpty()) return null;
        T top = m_heap.get(0); //Access of ArrayList, get(i), from any index i is O(1)  
	swapHeapElements(0, m_heap.size() - 1); //Put last element on top
	m_heap.remove(m_heap.size() - 1); //Remove LAST index is O(1) 
	//Swap down with the largest child until it is bigger than its largest child
	int i = 0;
	int largestchild = largestChild(i, m_heap.size());
	while ((largestchild > 0)&&(largestchild < m_heap.size())&&
               (m_heap.get(i).compareTo(m_heap.get(largestchild)) < 0)) {
            swapHeapElements(i, largestchild);        //swap values
            i = largestchild;                         //go down to child
            largestchild = largestChild(i, m_heap.size());       //find new largest child
        }
	return top; //return old top, which was the biggest number in the heap before it was removed
    }
    //Add element as last and then move up as long as it is bigger than its parent 
    public void addElement(T val) {
        m_heap.add(val);
	int i = m_heap.size() - 1;
	int parent = parent(i);
	while ((m_heap.get(i).compareTo(m_heap.get(parent)) > 0)&&(i > 0)) {
            swapHeapElements(i, parent);
            i = parent;
            parent = parent(i);
	}
    }
    //Utilities
    private void swapHeapElements(int i, int j) { m_heap.set(i, m_heap.set(j, m_heap.get(i))); }
    private int parent(int child) {      return (child - 1)/2; }
    private int leftChild(int parent) {  return 2*parent + 1; }
    private int rightChild(int parent) { return 2*parent + 2; }
    protected int largestChild(int parent, int N) {
	int li = leftChild(parent);
	int ri = rightChild(parent);
	if (li >= N) return -1;    //dessa 2 rader e 
	if (ri >= N) return li;    //mycket viktiga
	if (m_heap.get(ri).compareTo(m_heap.get(li)) < 0) return li;
	return ri;
    }  
}
